package com.ctrip.demo.leetcode;

import java.lang.reflect.ParameterizedType;
import java.sql.ResultSet;

public class LeetCode2044 {

    public static void main(String[] args) {

        System.out.println(new LeetCode2044().countMaxOrSubsets(new int[]{3, 1}));
        System.out.println(new LeetCode2044().countMaxOrSubsetsToBack(new int[]{3, 1}));

    }

    public int countMaxOrSubsets(int[] nums) {

        int n = nums.length, mask = 1 << n;

        int max =0, res = 0;

        for (int i = 0; i < mask; i++) {
            int cur = 0;
            for (int j = 0; j < n; j++) {
                if (((i >> j) & 1) == 1) {
                    cur |= nums[j];
                }
            }
            if (cur > max) {
                max = cur;
                res = 1;
            } else if (cur == max) {
                res ++;
            }
        }
        return res;
    }

    class Result {
        int max;
        int cnt;
        public Result() {
            this.max = 0;
            this.cnt = 0;
        }
    }
    public int countMaxOrSubsetsToBack(int[] nums) {

        Result res = new Result();
        backtrack(nums, res, 0, 0);
        return  res.cnt;
    }

    private void backtrack(int[] nums, Result res, int start, int xor) {
        if (start == nums.length) {
            if (xor == res.max) {
                res.cnt ++;
            } else if (xor > res.max) {
                res.cnt = 1;
                res.max = xor;
            }
            return;
        }

        // select nums[start]
        backtrack(nums,res,start + 1, (xor | nums[start]));
        // not select nums[start]
        backtrack(nums, res, start+1, xor);
    }
}
